#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int* lee_cadena(); //Pide el arreglo al usuario
void burbuja(int *lista); //método de la burbuja
void insercion(int *lista); //método de  inserción
void quick_sort(int *lista,int izq,int der); //metodo quicksort
int pivot(int *lista, int izq, int der);     //complemento a quicksort para determinar el pivote
void pruebas(void);	//pruebas de los métodos
int iguales(int *lista1,int *lista2); //comparar si son iguales 2 arreglos
void imprime(int *list);		//muestra en pantalla un arreglo
int tam;
int main(void){
int	*list,opcion;
	while(1){	//el menú de opciones
		printf("Qué método de ordenamiento utilizarás\n");
		printf("1-Burbuja\t2-Inserción\t3-Quicksort\t4-Pruebas\n\t:");
		scanf("%d",&opcion);
		switch(opcion){
			case 1:
			list=lee_cadena();
			burbuja(list);
			break;
			case 2:
			list=lee_cadena();
			insercion(list);
			break;
			case 3:
			list=lee_cadena();
			quick_sort(list,0,tam-1);
			break;
			case 4:
			pruebas();
			exit(0);
			break;
			default:
			exit(1);	
		}
		printf("la cadena ordenada es: ");
		imprime(list);
		printf("\n\n");
	}
  return(0);
}
//compara de 2 en 2 y va subiendo los mas grandes en la lista 
void burbuja(int *lista){
	int i,j,aux;
	for(i=0;i<tam-1;i++){
		for(j=0;j<tam-1-i;j++){
			if(lista[j+1]<lista[j]){ 
				aux=lista[j];
				lista[j]=lista[j+1];
				lista[j+1]=aux;}
		}
	}
}
//Toma un indice que se compara con sus antecesores, cambia el indice 
//cuando ha comparado con sus antecesores y algun antecesor es mayor que el
void insercion(int *lista){
	int i,j,indice;
	for(i=1;i<tam;i++){
		indice=lista[i];
		for(j=i-1;j>=0 && lista[j]>indice;j--){
			lista[j+1]=lista[j];
		}
		lista[j+1]=indice;
	}
}

void quick_sort(int *lista,int izq,int der){
	int pivote;
    if(izq < der){
       pivote=pivot(lista, izq, der); //determina el pivote para partir en 2 el arreglo
       quick_sort(lista, izq, pivote-1);
       quick_sort(lista, pivote+1, der);
    }
}
int pivot(int *lista, int izq, int der)
{
   int i,pivote,valor_pivote,aux;
   pivote = izq;		//toma como pivote el primer num de la partición
   valor_pivote = lista[pivote];
   for (i=izq+1; i<=der; i++){
       if (lista[i] < valor_pivote){ //selecciona el siguiente pivote en base al pivote actual
               pivote++;
               aux=lista[i];
               lista[i]=lista[pivote];
               lista[pivote]=aux;
       }
   }
   aux=lista[izq];
   lista[izq]=lista[pivote];
   lista[pivote]=aux;
   return pivote;
}
void pruebas(void){
	tam=10;
	int result[10]={0,1,2,3,4,5,6,7,8,9};
	int	lista1[10]={9,8,7,6,5,4,3,2,1,0};
	printf("\nCadena de entrada: ");
	imprime(lista1);
	printf("\nCadena   esperada: ");
	imprime(result);
	printf("\nProbando burbuja: ");
		burbuja(lista1);
		iguales(lista1,result);
	printf("\nProbando inserción: ");
		int	lista2[10]={9,8,7,6,5,4,3,2,1,0};
		insercion(lista2);
		iguales(lista2,result);		//compara si los arreglos son iguales
	printf("\nProbando quicksort: ");
		int	lista3[10]={9,8,7,6,5,4,3,2,1,0};
		quick_sort(lista3,0,tam-1);
		iguales(lista3,result);
}
int iguales(int *lista1,int *lista2){
	int j;
	for(j = 0; j < tam; j++) {
        if(lista1[j]!=lista2[j]){
			printf("Error en la prueba");
			return(0);
		} 
    }
	printf("Prueba aprobada");
	return (1);
}
void imprime(int *list){
    int j;
    for(j = 0; j < tam; j++) {;
        printf("%d ",list[j]); 
    }
}
int* lee_cadena(){
	int i=1; 		//variables de iteración
	char entrada[81];
	int *lista; 		//apuntador a la lista
    
    printf("Ingresa el tamaño de la lista\n");
    scanf("%d",&tam);
    printf("Ingresa los números separados por comas:\n");
    scanf(" %[^\n]",&entrada);    
    
    lista = (int *)malloc(tam * sizeof(int)); //reservamos la memoria
    *lista = atoi(strtok(entrada,","));		//toma el primer token lo convierte y guarda
    i=1;
    while(i<tam) { //continua buscando tokens
        *(lista+i) = atoi(strtok(NULL,","));
        i++;
    }
    return lista;
}
